Week 10 - Lec.27 & Lec.28

TOC

▶︎
all
running...

Lec.27 - Introduction to Graph

Introduction

Graph: A set of nodes (a.k.a. vertices) connected pairwise by edges:

Path: A sequence of vertices connected by edges

Cycle: A path whose first and last vertices are the same:

Two vertices are connected if there is a path between them:

graph-types

Problems

Examples

Facebook: Connectivity between cities

facebook-connectivity

Scientific journals' click through rates

Graph Representation

Graph API

Common convention: Number nodes irrespective of label

Graph API

public class Graph {
    
    /** Creates empty graph with `V` vertices */
    public Graph(int V);
    
    /** Adds an edge `v`-`w` */
    public void addEdge(int v, int w);
    
    /** Vertices adjacent to `v` */
    Iterable<Integer> adj(int v);
    
    /** Returns the number of vertices */
    int V();
    
    /** Returns the number of edges */
    int E();
}

Example client

/** Returns the degree of vertex `v` in graph `G` */
public static int degree(Graph G, int v) {
    int degree = 0;
    for (int w : G.adf()) {
        degree += 1;
    }
    return degree;
}

Graph Representations

Representation 1: Adjacency Matrix

v\w 0 1 2 3
0 0 1 0 0
1 1 0 1space 0
2 0 1space 0 1
3 0 0 1 0

Representation 2: Edge Set

Collection of all edges:

Representation 3: Adjacency List

Common approach: Maintain array of lists indexed by vertex number:

Graph Representation
img img

Runtimes

Printing an entire graph

for (int v = 0; v < G.V(); v += 1) {
    for (int w : G.adj(v)) {
        System.out.println(v + "-" + w);
    }
}

Runtime of Printing An Entire Graph

How to interpret Θ(V+E)\Theta(V + E):

Runtime of Basic Graph Operations

Representation addEdge(s, t) for(w : adf(v)) printGraph() hasEdge(s, t) Space used
Adjacency matrix Θ(1)\Theta(1) Θ(V)\Theta(V) Θ(V2)\Theta(V^2) Θ(1)\Theta(1) Θ(V2)\Theta(V^2)
Edge Set Θ(1)\Theta(1) Θ(E)\Theta(E) Θ(E)\Theta(E) Θ(E)\Theta(E) Θ(E)\Theta(E)
Adjacency list Θ(1)\Theta(1) Θ(1)\Theta(1) to Θ(V)\Theta(V) Θ(V+E)\Theta(V + E) Θ(degree(v))\Theta({\rm degree}(v)) Θ(V+E)\Theta(V + E)

(Note: printGraph() and hasEdge(s, t) are not part of the Graph class's API)

In practice, adjacency list is most common:

Lec.28 - Graph Traversal

Depth First Traversal

s-t Path Problem

Suppose we want to know if there exists a path from vertex s = 0 to vertex t = 7:
s-t-problem

Wrong idea
  1. Check s == t, if so, return true
  2. Check all of s's neighbors for connectivity to t

=> Fail into infinite loop...

Improved idea: demo
  1. Mark s
  2. Check s == t, if so, return true
  3. Check all of s's unmarked neighbors for connectivity to `t

=> This idea of exploring the entire subgraph for each neighbor is known as Depth First Search traversal.

Implementation

Common design pattern in graph algorithms: Decouple type from processing algorithm:

Recursive Implementation: demo

public class DepthFirstPaths {
    
    private boolean[] marked; // Tracks marked vertices
    private int[] edgeTo; // Tracks from which vertex the path came to an edge
    private int s;

    /** Finds all paths from `G`'s vertex `s` */
    public DepthFirstPaths(Graph G, int s) {
        ...  // Data structure initialization
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!markded[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    /** Checks there is a path from `s` to `t` */
    public boolean hasPathTo(int t) {
        return marked[t];
    }

    /** Returns path from `s` to `v` (if any) */
    public Iterable<Integer> pathTo(int t) {
        ...
    }

}

Preorder & Postorder Traversal

dfs-traversal

Topological Sort

Topological Sort Problem

Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w:

topological-sort-example

Solution

Perform DFS traversals from every vertex (with indegree 0), NOT clearing markings in between traversals:

topological-sort-demo-1
topological-sort-demo-2

Why Topological Sort

Can think of this procedure as sorting our nodes so that they appear in an order consistent with edge:

topological-sort-diagram

Implementation

public class DepthFirstPaths {
    
    private boolean[] marked;
    private Stack<Integer> reversePostorder;  // Use a stack instead of a list
    
    public DepthFirstPaths(Graph G) {
        reversePostorder = new Stack<>();
        marked = new boolean[G.V()];
        
        for (int v = 0; v < G.V(); v += 1) {
            if (!marked[v]) { dfs(G, v); }  // Perform DFS from all unmarked vertices
        }
    }
    
    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) { dfs(G, w); }
        }
        reversePostorder.push(v);  // 'Visit' vertex by pushing it in a stack
    }
    
    public Iterable<Integer> reversePostorder() {
        return reversePostorder;
    }
    
}

Shortest Path Problem

Given the graph below, find the shortest path from 0 to every other vertex:
shortest-path-example

Solution

Level-order provides the shortest paths from 0 to every reachable vertex from 0 by definition !: "Level order" is referred as "the order visited by Breadth First Search"

Breadth First Search demo

Implementation

public class BreadthFirstPaths {

    private boolean[] marked;
    private int[] edgeTo;

    ...

    private void bfs(Graph G, int s) {
        Queue<Integer> fringe = new Queue<>();
        fringe.enqueue(s);
        marked[s] = true;

        while(!fringe.isEmpty()) {
            int v = fringe.dequeue();
            for (int w : G.adj(v)) {
                fringe.enqueue(w);
                marked[w] = true;
                edgeTo[w] = v;
            }
        }
    }

}

Efficiency of Graph Problems

Problem Description Efficiency
s-t paths Find a path from s to every reachable vertex O(V+E)O(V + E) time
Θ(V)\Theta(V) space
Topological sort Find an ordering of vertices consistent with directed edges
s-t shortest path Find a shortest path from s to every reachable vertex